package easy.demo02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: wfmiss
 * @Date: 2023/12/11/10:56
 * @Description:
 * 题目来源：力扣 https://leetcode.cn/problems/valid-parentheses/
 * 20. 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 1、左括号必须用相同类型的右括号闭合。
 * 2、左括号必须以正确的顺序闭合。
 * 3、每个右括号都有一个对应的相同类型的左括号。
 */
public class Solution {
    public static void main(String[] args) {
        /**
         * 测试用例：
         * 示例 1：
         * 输入：s = "()"
         * 输出：true
         *
         * 示例 2：
         * 输入：s = "([]{})"
         * 输出：true
         *
         * 示例 3：
         * 输入：s = "(]"
         * 输出：false
         */
        System.out.println(isValid("([]{})"));
    }

    public static boolean isValid(String s) {
        // 判断字符串长度，小于2或字符长度为奇数直接返回false
        if (s.length() < 2 || s.length() % 2 == 1) return false;
        // Stack链表 用于模拟堆栈存储规则，先进后出原则
        ArrayList<Character> Stack = new ArrayList<>();
        // 遍历s字符串里每一个字符
        for (int i = 0; i < s.length(); i++) {
            // 判断是那种括号
            switch (s.charAt(i)) {
                case '(':
                case '[':
                case '{':
                    // 只有这三种括号可以进堆
                    Stack.add(s.charAt(i));
                    break;
                case ')':
                case ']':
                case '}':
                    // 当进入符号为以上条件时并且堆栈（Stack）为空，则返回false
                    if (Stack.isEmpty()) return false;
                    break;
            }
            // 堆栈（Stack）不为空才执行
            if (!Stack.isEmpty()) {
                switch (s.charAt(i)) {
                    /**
                     * 将当前括号【')',']','}'】类型与堆栈（Stack）末尾符号【'(','[','{'】进行匹配,
                     * 匹配成功 则移除堆栈（Stack）末尾符号【'(','[','{'】
                     * 匹配失败 则返回false
                     */
                    case ')':
                        if (Stack.get(Stack.size() - 1) == '(') Stack.remove(Stack.size() - 1);
                        else return false;
                        break;
                    case ']':
                        if (Stack.get(Stack.size() - 1) == '[') Stack.remove(Stack.size() - 1);
                        else return false;
                        break;
                    case '}':
                        if (Stack.get(Stack.size() - 1) == '{') Stack.remove(Stack.size() - 1);
                        else return false;
                        break;
                }
            }
        }
        // 以上程序运行结束后堆栈（Stack）不为空，则表示还有括号为匹配上 返回 false
        if (!Stack.isEmpty()) return false;
        // 堆栈（Stack）为空，所有括号均匹配完成
        return true;
    }
}
